Overlay networks are useful in creating virtual networks over other networks, such as the Internet or a corporate network. Such overlay networks have been considered as a means of improving Internet routing, particularly for bandwidth-demanding applications such as video conferencing, multi-party games, content distribution, distributed simulations, etc. In an overlay network, data are typically disseminated from a single source to multiple receivers via a relay tree. Although an overlay network cannot control how data packets are routed over the underlying network (i.e., the Internet) between two overlay network nodes, a relay tree can control the sequence of overlay network nodes a packet traverses in order to reach its destination. The various paths or links of an overlay network may need to be reorganized from time to time to improve performance as underlying network characteristics change, and/or address problems such as failed nodes or pathways. But transitioning or switching from one overlay network to another often results in the inefficiencies of duplicate and/or lost packets and re-transmission of packets. It is desirable to avoid such inefficiencies.